package com.xj.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

/**
 * 路径总和 III
 */
public class L437_二叉树的路径之和等于target的不完全路径的总个数 {

    /**
     * 给定一个二叉树，它的每个结点都存放着一个整数值。
     * <p>
     * 找出路径和等于给定数值的路径总数。
     * <p>
     * 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     * <p>
     * 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     * <p>
     * 示例：
     * <p>
     * root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
     * <p>
     * 10
     * /  \
     * 5   -3
     * / \    \
     * 3   2   11
     * / \   \
     * 3  -2   1
     * <p>
     * 返回 3。和等于 8 的路径有:
     * <p>
     * 1.  5 -> 3
     * 2.  5 -> 2 -> 1
     * 3.  -3 -> 11
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.left.left = new TreeNode(3);
        root.left.left.right = new TreeNode(-2);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(1);
        root.right = new TreeNode(-3);
        root.right.right = new TreeNode(11);

        System.out.println(pathSum(root, 8));
        System.out.println(pathSumGood(root,8));
    }

    //自己的解法：2重循环，从上到下的递归减法，看最终是否为0
    public static int pathSum(TreeNode root, int sum) {
        //使用队列进行层次遍历找到所有节点
        List<TreeNode> list = new ArrayList<>();

        Queue<TreeNode> queue = new ArrayDeque<>();
        if (root != null) {
            queue.add(root);
        }
        while (!queue.isEmpty()) {
            TreeNode tmp = queue.poll();
            list.add(tmp);

            if (tmp.left != null) {
                queue.add(tmp.left);
            }
            if (tmp.right != null) {
                queue.add(tmp.right);
            }
        }

        //循环处理每个节点
        int result=0;
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            result+=findTreePathSumCountFromRoot(node,sum);
        }
        return result;
    }

    //检查一颗树路径之和等于某个值的总个数
    public static int findTreePathSumCountFromRoot(TreeNode node, int sum) {
        if (node == null) {
            return 0;
        }
        sum -= node.val;
        int count=0;
        if (sum==0) {
            count=1;
        }
        return findTreePathSumCountFromRoot(node.left, sum) + findTreePathSumCountFromRoot(node.right, sum)+count;
    }

    //官方解法：从下往上到根节点，递归解法,核心是数组
    public static int pathSumGood(TreeNode root, int sum) {
        return pathSumDfs(root, sum, new int[1000], 0);
    }

    public static int pathSumDfs(TreeNode root, int sum, int[] array/*保存路径*/, int p/*指向路径终点*/) {
        if (root == null) {
            return 0;
        }
        int tmp = root.val;
        int n = root.val == sum ? 1 : 0;
        for (int i = p - 1; i >= 0; i--) {
            tmp += array[i];
            if (tmp == sum) {
                n++;
            }
        }
        array[p] = root.val;
        int n1 = pathSumDfs(root.left, sum, array, p + 1);
        int n2 = pathSumDfs(root.right, sum, array, p + 1);
        return n + n1 + n2;
    }

}
